理工學(xué)院楊升浩教授團(tuán)隊(duì)的研究論文被密碼學(xué)領(lǐng)域頂會(huì)Eurocrypt 2026錄用
理工學(xué)院楊升浩教授研究團(tuán)隊(duì)在密碼學(xué)基礎(chǔ)理論研究中取得重要進(jìn)展。Goldreich偽隨機(jī)生成器是密碼學(xué)中一項(xiàng)基礎(chǔ)性的構(gòu)造方法。團(tuán)隊(duì)博士生李墨、呂世瀚提出了一種名為Group-and-Solve（GAS）的全新攻擊框架，高效破解了Goldreich偽隨機(jī)生成器的一類(lèi)重要實(shí)例。該框架基于概率分析與代數(shù)求解技術(shù)，不僅成功攻破了Eurocrypt 2024會(huì)議提出的Silent OT協(xié)議參數(shù)，還揭示了多個(gè)FiLIP密碼實(shí)例無(wú)法達(dá)到其所聲稱(chēng)的安全性。相關(guān)研究成果已撰寫(xiě)成論文Attacks on Goldreich’s Pseudorandom Generators by Grouping and Solving，并被國(guó)際密碼學(xué)頂級(jí)會(huì)議Eurocrypt 2026正式錄用。這是港中大（深圳）首次被Eurocrypt會(huì)議錄用論文，標(biāo)志著學(xué)校在國(guó)際密碼學(xué)理論研究領(lǐng)域的原創(chuàng)性成果獲得旗艦會(huì)議認(rèn)可。
?
該研究由付希明博士（現(xiàn)為哈爾濱工業(yè)大學(xué)（深圳）副教授）主導(dǎo)，其在港中大（深圳）理工學(xué)院楊升浩教授課題組從事博士后研究期間，指導(dǎo)博士生李墨、呂世瀚共同完成項(xiàng)目工作。
?
一、會(huì)議介紹
Eurocrypt （歐洲密碼學(xué)年會(huì)，全稱(chēng)為“Annual International Conference on the Theory and Applications of Cryptographic Techniques”）是國(guó)際密碼學(xué)研究學(xué)會(huì)（IACR）主辦的三大旗艦會(huì)議之一，與美洲的CRYPTO、亞洲的ASIACRYPT并稱(chēng)為密碼學(xué)領(lǐng)域的“三大頂會(huì)”。該會(huì)議是中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）推薦的A類(lèi)會(huì)議，代表了全球密碼學(xué)理論與應(yīng)用研究的頂尖水平，在學(xué)界和業(yè)界均享有崇高聲譽(yù)。
?
二、研究背景
Goldreich偽隨機(jī)數(shù)生成器是一類(lèi)重要的密碼學(xué)原語(yǔ)，尤其是具有多項(xiàng)式延展度的該類(lèi)生成器在secure computation with constant computational overhead、indistinguishability obfuscation (iO)、MPC-friendly primitives和cryptographic capsules領(lǐng)域有廣泛的應(yīng)用。構(gòu)造該類(lèi)隨機(jī)數(shù)生成器的關(guān)鍵是構(gòu)造一個(gè)具有局部性的謂詞函數(shù)，其中主要構(gòu)造有XOR-AND（FOCS 2003）和XOR-THR（STOC 2016）。針對(duì)XOR-AND的安全性分析，有學(xué)者提出了Guess-and-Determine和Guess-and-Decode攻擊。然而這兩類(lèi)攻擊主要針對(duì)小局部性的謂詞，且依賴(lài)于方程的稀疏性和無(wú)噪假設(shè)。然而，對(duì)于大局部性的XOR-THR結(jié)構(gòu)，隨著參數(shù)增長(zhǎng)，這些方法的攻擊復(fù)雜度接近窮舉。因此，針對(duì)基于XOR-THR的Goldreich偽隨機(jī)數(shù)生成器的安全性分析是公開(kāi)難題。
?
三、研究?jī)?nèi)容
本研究提出了全新的Group-and-Solve（GAS）攻擊框架，通過(guò)構(gòu)造并求解低噪聲的含噪線(xiàn)性方程組來(lái)恢復(fù)隨機(jī)數(shù)種子，其核心創(chuàng)新包括：
- 高效的偏差放大機(jī)制：論文觀(guān)察到，當(dāng) XOR-THR謂詞的部分輸入位被固定時(shí)，原本平衡的非線(xiàn)性函數(shù)會(huì)表現(xiàn)出顯著的不平衡性。通過(guò)將輸出比特根據(jù)公共輸入進(jìn)行“分組”，攻擊者可以獲得一組偏差極大的噪聲方程，從而構(gòu)造了低噪聲的線(xiàn)性方程組。顯著降低LPN問(wèn)題的求解難度。
- 定制化的LPN求解器：含噪線(xiàn)性方程組求解可以規(guī)約到LPN問(wèn)題，是密碼學(xué)和理論計(jì)算機(jī)中的經(jīng)典困難問(wèn)題。針對(duì)分組后“樣本量少、偏差大”的特點(diǎn)，研究團(tuán)隊(duì)改進(jìn)了高斯消元法，設(shè)計(jì)了專(zhuān)門(mén)的求解策略。與傳統(tǒng)的 BKW算法相比，新方法不需要海量的內(nèi)存和方程數(shù)量，完美適配了輸出長(zhǎng)度受限的約束。
- 跨方案的普適性攻擊：該框架不僅適用于Eurocrypt 2024中用于構(gòu)建高效Silent OT協(xié)議的參數(shù)實(shí)例，還被成功適配到具有白化噪聲結(jié)構(gòu)的FiLIP密碼中，對(duì)于大多數(shù)此密碼實(shí)例，攻擊是成功且高效的。
?
四、研究結(jié)論
本研究提出的Group-and-Solve（GAS）攻擊框架，證明了基于特定謂詞函數(shù)的Goldreich PRG及其相關(guān)密碼協(xié)議（如特定的Silent OT和FiLIP）是不安全的。該工作體現(xiàn)了研究團(tuán)隊(duì)在密碼學(xué)基礎(chǔ)理論和計(jì)算機(jī)科學(xué)中經(jīng)典困難問(wèn)題求解領(lǐng)域的創(chuàng)新能力，其中涉及到LPN求解和ISD求解算法更是后量子密碼的基礎(chǔ)問(wèn)題。未來(lái)，團(tuán)隊(duì)將繼續(xù)探索后量子時(shí)代下的密碼安全邊界，為構(gòu)建更可信的數(shù)字安全基礎(chǔ)設(shè)施提供理論支撐。
?
五、作者簡(jiǎn)介
付希明教授
付希明于2011年在清華大學(xué)電子工程系獲得工學(xué)學(xué)士學(xué)位，2018年在清華大學(xué)計(jì)算機(jī)系獲得工學(xué)博士學(xué)位。2019-2021年期間，他在香港中文大學(xué)（深圳）從事博士后研究工作。2022年，他加入哈爾濱工業(yè)大學(xué)（深圳）計(jì)算機(jī)學(xué)院任助理教授，現(xiàn)為網(wǎng)絡(luò)空間安全研究院副教授。他的研究領(lǐng)域包括密碼學(xué)與計(jì)算理論、隱私計(jì)算、編碼理論與技術(shù)、共識(shí)機(jī)制。
?
理工學(xué)院2026屆計(jì)算機(jī)與信息工程專(zhuān)業(yè)博士畢業(yè)生李墨
李墨于2020年在新南威爾士大學(xué)獲得工學(xué)學(xué)士學(xué)位，2021年開(kāi)始在香港中文大學(xué)（深圳）攻讀博士學(xué)位。他的研究興趣包括：分布式系統(tǒng)中的一致性問(wèn)題和容錯(cuò)問(wèn)題、密碼學(xué)原語(yǔ)的設(shè)計(jì)和應(yīng)用。
?
理工學(xué)院2025級(jí)計(jì)算機(jī)與信息工程專(zhuān)業(yè)在讀博士生呂世瀚
呂世瀚的研究興趣包括密碼分析、密碼學(xué)與機(jī)器學(xué)習(xí)的結(jié)合。
?
?
供稿 | 楊升浩教授團(tuán)隊(duì)
?
